package sort

// 快速排序
type QuickSort struct {
}

func (q *QuickSort) Sort(nums []int) {
	internalSort(nums, 0, len(nums)-1)
}

func internalSort(nums []int, left int, right int) []int {
	if left < right {
		i := doSort(nums, left, right)
		internalSort(nums, left, i-1)
		internalSort(nums, i+1, right)
	}
	return nums
}

func doSort(nums []int, left, right int) int {
	pivot := left
	index := pivot + 1

	for i := index; i <= right; i++ {
		if nums[i] < nums[pivot] {
			Swap(nums, i, index)
			index++
		}
	}

	Swap(nums, pivot, index-1)

	return index - 1
}
